#include <iostream>
using namespace std;

int numDistinct(string S, string T);

int main(){
    cout<<numDistinct("aabb","ab")<<endl;
    return 0;
}

int numDistinct(string S, string T) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(T.size() == 0 || T.size() > S.size())
        return 0;

    int *pCountR = new int[S.size()];
    int *pCountW = new int[S.size()];

    if(S[0] == T[0])
        pCountR[0] = 1;
    else
        pCountR[0] = 0;
    // first line
    for(int i=1; i<S.size(); ++i){
        if(S[i] == T[0])
            pCountR[i] = pCountR[i-1] + 1;
        else
            pCountR[i] = pCountR[i-1];
    }
    // later lines
    for(int j=1; j<T.size(); ++j){
        pCountW[j-1] = 0;
        for(int i=j; i<S.size(); ++i){
            pCountW[i] = pCountW[i-1] 
                + (S[i] == T[j] ? pCountR[i-1]:0);
        }
        int *pTmp = pCountR;
        pCountR = pCountW;
        pCountW = pTmp;
    }
    int res = pCountR[S.size()-1];
    delete []pCountR;
    delete []pCountW;

    return res;
}
